package com.company.ljh.medium;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @description:
 * 208.实现前缀树
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2024/2/20 12:43
 * @version:1.0
 */
public class 前缀树 {
    private Node head;
    private class Node{
        //标记当前节点是否为词组的结束节点
        boolean isEnd;
        //由于只包括小写字母，可以用26位长度的数组代替
        Map<Character,Node> childrenNodes;
        char val;
        public Node(boolean isEnd,char val){
            this.isEnd = isEnd;
            this.val = val;
            childrenNodes = new HashMap<>();
        }
    }
    public 前缀树() {
        head = new Node(false,'0');
    }

    public void insert(String word) {
        char[] chars = word.toCharArray();
        Node start = head;
        for(int i = 0;i < chars.length;i++){
            if(!start.childrenNodes.containsKey(chars[i])){
                Node node = new Node(false, chars[i]);
                start.childrenNodes.put(chars[i],node);

            }
            start = start.childrenNodes.get(chars[i]);
            if (i == chars.length - 1){
                start.isEnd = true;
            }
        }
    }

    public boolean search(String word) {
        char[] chars = word.toCharArray();
        Node start = head;
        for(int i = 0;i < chars.length;i++){
            if(!start.childrenNodes.containsKey(chars[i])){
                return false;
            }
            start = start.childrenNodes.get(chars[i]);
            if(i ==  chars.length - 1 && start.isEnd){
                return true;
            }
        }
        return false;
    }

    public boolean startsWith(String prefix) {
        char[] chars = prefix.toCharArray();
        Node start = head;
        for(int i = 0;i < chars.length;i++){
            if(!start.childrenNodes.containsKey(chars[i])){
                return false;
            }
            start = start.childrenNodes.get(chars[i]);
        }
        return true;
    }

    public static void main(String[] args) {
        前缀树 s = new 前缀树();
        s.insert("ppap");
        s.insert("ppa");
        s.insert("cpa");
        System.out.println(s.search("ppa"));;
        System.out.println(s.startsWith("ppa"));;;
        System.out.println(s.search("ppap"));;;
    }
}
